package com.francis;

import java.util.Arrays;

/**
 * 最大子数组问题
 *
 * @author francis
 * @create 2018-03-07 20:44
 **/
public class MaxSubArray {

    /**
     * 分治法求解：
     * 1.求左边数组的最大子数组
     * 2.求右边数组的最大子数组
     * 3.求跨过中间节点的最大子数组子数组
     * 4.求max(1,2,3)即得到结果
     * @return
     */
    public static int[] maxSubArray1(int[] array, int start, int middle, int last) {
        if(middle < start || last < middle || array == null || array.length <= last) {
            throw new IllegalArgumentException("argument should matches: array is not null && middle <= start <= last < array.length!");
        }

        int[] left_max_array, right_max_array, middle_max_array;

        if(middle - start > 1) {
            left_max_array = maxSubArray1(array, start, (middle + start - 1) / 2, middle - 1);
        } else {
            left_max_array = new int[]{array[start]};
        }

        if(last - middle > 1) {
            right_max_array = maxSubArray1(array, middle + 1, (middle + last + 1) / 2, last);
        } else {
            right_max_array = new int[]{array[last]};
        }

        int max_start = middle, middle_left_max_sum = 0, left_sum = 0;
        int max_end = middle, middle_right_max_sum = 0, right_sum = 0;

        for(int i = middle; i >= start; i--) { // 中间往左求包含中间节点的最大子数组
            left_sum += array[i];
            if(left_sum > middle_left_max_sum) {
                max_start = i;
                middle_left_max_sum = left_sum;
            }
        }

        for(int i = middle; i <= last; i++) { // 中间往右求包含中间节点的最大子数组
            right_sum += array[i];
            if(right_sum > middle_right_max_sum) {
                max_end = i;
                middle_right_max_sum = right_sum;
            }
        }

        middle_max_array = new int[max_end - max_start + 1];
        for(int i = 0; i < middle_max_array.length; i++) {
            middle_max_array[i] = array[max_start + i];
        }

        int left_array_max_sum = sum(left_max_array);
        int right_array_max_sum = sum(right_max_array);
        int middle_array_max_sum = sum(middle_max_array);
        if(left_array_max_sum > right_array_max_sum && left_array_max_sum > middle_array_max_sum) {
            return left_max_array;
        } else if(right_array_max_sum > middle_array_max_sum) {
            return right_max_array;
        } else {
            return middle_max_array;
        }
    }

    /**
     * 非递归算法，线性求解，思路：已知前面a[0...i]的最大子数组max(a[0->i])，a[0...i + 1]的最大子数组必在max(a[0->i])与包含a[i+1]的最大子数组中间，每次循环求解包含a[i+1]的子数组与之前的对比即可。
     * @param array
     * @return
     */
    public static int[] maxSubArray2(int[] array) {
        if(array == null && array.length == 0) {
            throw new IllegalArgumentException("argument should matches: array is not null and array.length != 0!");
        }

        int max_start_index = 0, max_end_index = 0;
        int max_sum = array[0];

        for(int i = 1; i < array.length; i ++) {
            int sum = 0, max_sub_array_start = -1;
            for(int j = i; j >= 0; j--) {
                sum += array[j];
                if(sum > max_sum) {
                    max_sub_array_start = j;
                    max_sum = sum;
                }
            }

            if(max_sub_array_start >= 0) {
                max_start_index = max_sub_array_start;
                max_end_index = i;
            }
        }

        int[] max_array = new int[max_end_index - max_start_index + 1];
        for(int i = 0; i < max_array.length; i++) {
            max_array[i] = array[max_start_index + i];
        }

        return max_array;
    }

    private static int sum(int[]array) {
        if(array == null || array.length < 1) return 0;
        int result = 0;
        for (int i = 0; i < array.length; i++ ) {
            result += array[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] array = {1, -1, 2, 1, -3, 4, -5, 7, -5, 3, -1, -3, 8, -1};
        System.out.println(Arrays.toString(maxSubArray1(array, 0, array.length / 2, array.length - 1)));
        System.out.println(Arrays.toString(maxSubArray2(array)));
    }
}